package com.algorithm.dp;

import static com.google.common.primitives.Ints.min;

/**
 * 编辑距离,即给定一个单词,求将其变为另一个单词所需要的最小步数.(矩阵中最大正方形的状态转移方程与此相同)
 * 允许的操作有:
 * 删除一个字母;
 * 插入一个字母;
 * 替换一个字母
 */
public class Leveinshtein {
    public static void main(String[] args) {
        String word1 = "finish";
        String word2 = "fish";
        int min = editLength(word1, word2);
        System.out.println(min);
        min = minDistance(word1, word2);
        System.out.println(min);
    }

    /**
     * 难点在于找出状态转移方程:
     * 使用二维数组即可表示字符转换流程,若i为原字符串第i位,j为目标字符串j位
     * dp[i][j] = min{dp[i][j-1],dp[i-1][j-1],dp[i-1][j]} +1    if dp[i] != dp[j]
     *          = dp[i-1][j-1]                                  else
     * 删除一个字符dp[i][j] --> dp[i-1][j-1]
     * 插入一个字符dp[i][j] --> dp[i-1][j]
     * 替换一个字符dp[i][j] --> dp[i][j-1]
     * 若word1[i] == word2[j] 则在得到0至j-1的子字符串的基础上不需要额外操作(+0),否则需要进行一步替换操作(+1)
     *
     * @param word1
     * @param word2
     * @return
     */
    private static int editLength(String word1, String word2) {
        /**
         * +1 的意义:假设从空字符串到目标字符串的转换
         */
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i;
        }


        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                }
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + "\t");

            }
            System.out.println();

        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

    private static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();

        int[] cur = new int[m+1];
        for (int i = 1; i <= m; i++)
            cur[i] = i;

        /**
         * 相当于二维数组从左上往右下纵向扫描,cur先是保存着上一列的数据,然后逐渐被当前列数据替换.
         * 但是dp[i][j]依赖于dp[i-1][j-1]和dp[i][j-1],所以肯定会有一个被覆盖,
         * 此时使用一个pre保存dp[i-1][j-1]的值即可(这里使用了数组第一位保存)
         */
        for (int j = 1; j <= n; j++) {
            int pre = cur[0];
            cur[0] = j;
            for (int i = 1; i <= m; i++) {
                int temp = cur[i];
                if (word1.charAt(i-1) == word2.charAt(j-1))
                    cur[i] = pre;
                else
                    cur[i] = min(pre + 1, min(cur[i] + 1, cur[i - 1] + 1));
                pre = temp;
            }
        }
        for (int i = 0; i < cur.length; i++) {
            System.out.print(cur[i] +"\t");
        }
        return cur[m];
    }
}
